@Part[Eval, Root = "CLM.MSS"]
@Comment{Chapter of Spice Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇


@MyChapter[The Evaluator]


The mechanism that executes @xlisp programs is called the evaluator.
More precisely, the evaluator accepts a form and performs the
computation specified by the form.  This mechanism is made available
to the user through the function @f[eval].

The evaluator is typically implemented as an interpreter
that traverses the given form recursively, performing each step
of the computation as it goes.  An interpretive implementation is not
required, however.  A permissible alternative approach is
for the evaluator first to completely compile the form into
machine-executable code and then invoke the resulting code.
This technique virtually eliminates incompatibilities
between interpreted and compiled code, but also renders the @f[evalhook]
mechanism relatively useless.
Various mixed strategies are also possible.  All of these approaches
should produce the same results when executing a correct program,
but may produce different results for incorrect programs.
For example, the approaches may differ as to when macro calls
are expanded; macro definitions should not depend on the time
at which they are expanded.  Implementors should
document the evaluation strategy for each implementation.

@Section[Run-Time Evaluation of Forms]

The function @f[eval] is the main user interface to the evaluator.
Hooks are provided for user-supplied debugging routines
to obtain control during the execution of an interpretive evaluator.
The functions @f[evalhook] and @f[applyhook] provide alternative
interfaces to the evaluator mechanism for use by these debugging routines.

@Defun[Fun {eval⎇, Args {@i[form]⎇]
The @i[form] is evaluated in the current dynamic environment and
a null lexical environment.  Whatever results from the evaluation
is returned from the call to @f[eval].

Note that when you write a call to @f[eval] @i[two] levels
of evaluation occur on the argument form you write.
First the argument form is evaluated, as for arguments to any function,
by the usual argument evaluation mechanism
(which involves an implicit use of @f[eval]).  Then the argument
is passed to the @f[eval] function, where another evaluation occurs.
For example:
@lisp
(eval (list 'cdr (car '((quote (a . b)) c)))) @EV b
@endlisp
The argument form @f[(list 'cdr (car '((quote (a . b)) c)))] is evaluated
in the usual way to produce the argument @f[(cdr (quote (a . b)))];
this is then given to @f[eval] because @f[eval] is being called explicitly,
and @f[eval] evaluates its argument @f[(cdr (quote (a . b)))] to produce @f[b].

If all that is required for some application is
to obtain the current dynamic value of a given symbol, the function
@Funref[symbol-value] may be more efficient than @f[eval].
@Enddefun

@Defvar[Var {evalhook⎇]
@Defvar1[Var {applyhook⎇]
If the value of @var[evalhook] is not @false, then @f[eval] behaves
in a special way.  The non-@false value of @Var[evalhook] should be a function
that takes two arguments, a form and an environment;
this is called the @i[eval hook function].
When a form is to be evaluated (any form at all, even a number or a symbol),
whether implicitly or via an explicit call to @f[eval], no attempt
is made to evaluate the form.
Instead, the hook function is invoked and is passed the form to be evaluated
as its first argument.  The hook function is then responsible for
evaluating the form; whatever is returned by the hook function is assumed
to be the result of evaluating the form.

The variable @Var[applyhook] is similar to @Var[evalhook] but is used
when a function is about to be applied to arguments.
If the value of @var[applyhook] is not @false, then @f[eval] behaves
in a special way.  The non-@false value of @Var[applyhook] should be a function
that takes three arguments, a function, a list of arguments,
and an environment;
this is called the @i[apply hook function].
When a function is about to be applied to a list of arguments,
no attempt is made to apply the function.
Instead, the hook function is invoked and is passed the function and the list
of arguments
as its first and second arguments.  The hook function is then responsible for
evaluating the form; whatever is returned by the hook function is assumed
to be the result of evaluating the form.
The apply hook function is used only for application of ordinary functions
within @f[eval].  It is not used for applications via @Funref[apply] or
@Funref[funcall], for applications by such functions as @Funref[map] or
@Funref[reduce], or for invocation of macro-expansion functions
by either @f[eval] or @Funref[macroexpand].

The last argument passed to either kind of hook function contains information
about the lexical environment in an implementation-dependent format.
These arguments are suitable for the functions
@Funref[evalhook], @Funref[applyhook], and @Funref[macroexpand].

When either kind of hook function is invoked, both @var[evalhook]
and @var[applyhook] are rebound to the value @nil around the invocation
of the hook function.  This is so that the hook function will not be
invoked recursively on evaluations and applications that occur
in the course of executing the code of the hook function.
The functions @Funref[evalhook]
and @Funref[applyhook] are useful for performing recursive evaluations
and applications within the hook function.

The hook feature is provided as an aid to debugging.
The @Macref[step] facility is implemented using this hook.

If a non-local exit causes a throw back to the top level
of @xlisp, perhaps because an error could not
be corrected, then @var[evalhook] and @var[applyhook] are
automatically reset to @false as a safety feature.
@Enddefvar

@Defun[Fun {evalhook⎇, Args {@i[form] @i[evalhookfn] @i[applyhookfn] @optional @i[env]⎇]
@Defun1[Fun {applyhook⎇, Args {@i[function] @i[args] @i[evalhookfn] @i[applyhookfn] @optional @i[env]⎇]
The functions @f[evalhook] and @f[applyhook] are provided to make it
easier to exploit the hook feature.

In the case of @f[evalhook], the @i[form] is evaluated.
In the case of @f[applyhook], the @i[function] is applied to the
list of arguments @i[args].  In either case,
for the duration of the operation
the variable @var[evalhook] is bound to @i[evalhookfn], and
@var[applyhook] is bound to @i[applyhookfn].
Furthermore, the @i[env] argument
is used as the lexical environment for the operation;
@f[env] defaults to the null environment.
The check for a hook function is @i[bypassed] for the evaluation
of the @i[form] itself (for @f[evalhook]) or for the application
of the @i[function] to the @i[args] itself (for @f[applyhook]),
but not for subsidiary evaluations and applications.
such as evaluations of subforms.  It is this one-shot bypass that makes
@f[evalhook] and @f[applyhook] so useful.

Here is an example of a very simple tracing routine that uses just the
@f[evalhook] feature.
@lisp
(defvar *hooklevel* 0)

(defun hook (x)
  (let ((*evalhook* 'eval-hook-function))
    (eval x)))

(defun eval-hook-function (form @rest env)
  (let ((*hooklevel* (+ *hooklevel* 1)))
    (format *trace-output* "@tilde@;%@tilde@;V@@TForm:  @tilde@;S"
	    (* *hooklevel* 2) form)
    (let ((values (multiple-value-list
		     (evalhook form
			       #'eval-hook-function
			       @nil
			       env))))
      (format *trace-output* "@tilde@;%@tilde@;V@@TValue:@tilde@;@lbrace@tilde@;S @tilde@;@rbrace@;"
	      (* *hooklevel* 2) values)
      (values-list values))))
@endlisp
Using these routines, one might see the following interaction:
@lisp
(hook '(cons (floor *print-base* 2) 'b))
  Form:  (CONS (FLOOR *PRINT-BASE* 2) (QUOTE B))
    Form:  (FLOOR *PRINT-BASE* 3)
      Form:  *PRINT-BASE*
      Value: 10
      Form:  3
      Value: 3
    Value: 3 1
    Form:  (QUOTE B)
    Value: B
  Value: (3 . B)
(3 . B)
@endlisp
@Enddefun

@Defun[Fun {constantp⎇, Args {@i[object]⎇]
If the predicate @f[constantp] is true of an object,
then that object, when considered as a form to
be evaluated, always evaluates to the same thing;
it is a constant.
This includes self-evaluating objects such as numbers, characters,
strings, bit-vectors, and keywords, as well as all constant symbols
declared by @Macref[defconstant],
such as @conref[nil], @conref[t], and @conref[pi].
In addition, a list whose @i[car] is @f[quote],
such as @f[(quote foo)], is considered to be a constant.

If @f[constantp] is false of an object, then
that object, considered as a form,
might or might not always evaluate to the same thing.
@Enddefun

@Section[The Top-Level Loop]

Normally one interacts with @xlisp through a ``top-level
@f[read]-@f[eval]-@f[print] loop,'' so called because
it is the highest level of control and consists of an endless
loop that reads an expression, evaluates it, and prints the
results.  One has an effect on the state of the @xlisp system
only by invoking actions that have side effects.

The precise nature of the top-level loop for @clisp
is purposely not rigorously specified here so that implementors can
experiment to improve the user interface.
For example, an implementor may choose to require line-at-a-time
input, or may provide a fancy editor or complex graphics-display
interface.  An implementor may choose to provide
explicit prompts for input,
or may choose (as @maclisp does) not to clutter up the transcript
with prompts.

The top-level loop is required to trap all throws and recover gracefully.
It is also required to print all values resulting from evaluation of a form,
perhaps on separate lines.  If a form returns zero values, as little
as possible should be printed.

The following variables are maintained by the top-level loop
as a limited safety net, in case the user forgets to save an interesting input
expression or output value.  (Note that the names of some of these variables
violate the convention that names of global variables begin and end with
an asterisk.)  These are intended primarily for user interaction, which is why
they have short names.  Use of these variables should be avoided in programs.

@Defvar[Var {+⎇, Varlabel {#K⎇, Nostar]
@Defvar1[Var {++⎇, Varlabel {#K#K⎇, Nostar]
@Defvar1[Var {+++⎇, Varlabel {#K#K#K⎇, Nostar]
While a form is being evaluated by the top-level loop,
the variable @f[+] is bound to the previous form read by the loop.
The variable @f[++] holds the previous value of @f[+] (that is, the form
evaluated two interactions ago), and @f[+++] holds the previous value
of @f[++].
@enddefvar

@Defvar[Var {-⎇, Nostar]
While a form is being evaluated by the top-level loop,
the variable @f[-] is bound to the form itself; that is,
it is the value about to be given to @f[+] once this interaction
is done.
@Enddefvar

@Defvar[Var {*⎇, Nostar]
@Defvar1[Var {**⎇, Nostar]
@Defvar1[Var {***⎇, Nostar]
While a form is being evaluated by the top-level loop,
the variable @f[*] is bound to the result printed at the
end of the last time through the loop; that is, it is the value
produced by evaluating the form in @f[+].  If several values were produced,
@f[*] contains the first value only; @f[*] contains @nil if zero values
were produced.
The variable @f[**] holds the previous value of @f[*] (that is, the result
printed two interactions ago), and @f[***] holds the previous value
of @f[**].

If the evaluation of @f[+] is aborted for some reason,
then the values associated with @f[*], @f[**], and @f[***] are not updated;
they are updated only if the printing of values is at least begun (though not
necessarily completed).
@Enddefvar

@Defvar[Var {/⎇, Varlabel {#O⎇, Nostar]
@Defvar1[Var {//⎇, Varlabel {#O#O⎇, Nostar]
@Defvar1[Var {///⎇, Varlabel {#O#O#O⎇, Nostar]
While a form is being evaluated by the top-level loop,
the variable @f[/] is bound to a list of the results printed at the
end of the last time through the loop; that is, it is a list of all values
produced by evaluating the form in @f[+].  The value of @f[*] should
always be the same as the @i[car] of the value of @f[/].
The variable @f[//] holds the previous value of @f[/] (that is, the results
printed two interactions ago), and @f[///] holds the previous value
of @f[//].  Therefore the value of @f[**] should always be the same
as the @i[car] of @f[//], and similarly for @f[***] and @f[///].

If the evaluation of @f[+] is aborted for some reason,
then the values associated with @f[/], @f[//], and @f[///] are not updated;
they are updated only if the printing of values is at least begun (though not
necessarily completed).
@Enddefvar

As an example of the processing of these variables, consider the
following possible transcript, where @f[>] is a prompt by
the top-level loop for user input:
@lisp
>(cons - -)			;Interaction 1
((CONS - -) CONS - -)		; Cute, huh?

>(values)			;Interaction 2
				; There is nothing to print.
>(cons 'a 'b)			;Interaction 3
(A . B)				; There is a single value.

>(hairy-loop)↑G			;Interaction 4
### QUIT to top level.		; (User aborts the computation.)

>(floor 13 4)			;Interaction 5
3				; There are two values.
1
@endlisp
At this point we have:
@lisp
@tabdivide[3]
+++ @EV (cons 'a 'b)@\*** @EV NIL    @\/// @EV ()
++  @EV (hairy-loop)@\**  @EV (A . B)@\//  @EV ((A . B))
+   @EV (floor 13 4)@\*   @EV 3      @\/   @EV (3 1)
@endlisp